package thired.class14_matrix;

public class Class01_FibonacciProblem {
    public static int fibonacci(int n){
        if(n==0) return 0;
        if(n==1) return 1;
        return fibonacci(n-1)+fibonacci(n-2);
    }

    public static int fibonacci_dp(int n){
        int[] dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    public static int f3(int n){
        if(n==0) return 0;
        if(n==1) return 1;
        int[][] base     = new int[][]{
                {1,1},
                {1,0}
        };
        int[][] res = matrixPower(base, n - 2);
        return res[0][0] + res[1][0];
    }

    public static int[][] matrixPower(int[][] base, int n){
        int[][] res = new int[base.length][base[0].length];
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        int[][] t = base;
        for(;n!=0;n>>=1){
            if((n&1)!=0){
                res = multiply(res, t);
            }
            t = multiply(t, t);
        }
        return res;
    }

    public static int[][] multiply(int[][] a, int[][] b){
        int[][] c = new int[a.length][b[0].length];
        for(int i=0;i<a.length;i++){
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < a[0].length; k++) {
                    c[i][j] += a[i][k]*b[k][j];
                }
            }
        }
        return  c;
    }
    public static void main(String[] args) {
        System.out.println(fibonacci(5));
        System.out.println(fibonacci_dp(5));
        System.out.println(f3(5));
        System.out.println(fibonacci(10));
        System.out.println(fibonacci_dp(10));
        System.out.println(f3(10));
    }
}
